﻿#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
#include<map>
using namespace std;

//1.⻓度最⼩的⼦数组（medium）初写，无优化版本;
//class Solution {
//public:
//    int minSubArrayLen(int target, vector<int>& nums)
//    {
//        int left = 0;
//        int size = nums.size();
//        int ret = 0;
//        int right = left;
//        int sum = nums[right];
//        while (left < size)
//        {
//            while (sum < target && right < size - 1)
//            {
//                right++;
//                sum += nums[right];
//            }
//            if (sum >= target)
//            {
//                if (ret == 0)
//                    ret = right - left + 1;
//                else
//                {
//                    if (right - left + 1 < ret)
//                        ret = right - left + 1;
//                }
//            }
//            sum -= nums[left];
//            left++;
//        }
//        return ret;
//    }
//};
////优化代码;
//class Solution {
//public:
//    int minSubArrayLen(int target, vector<int>& nums)
//    {
//        int size = nums.size();
//        int sum = 0, ret = INT_MAX;
//        for (int left = 0, right = 0; right < size; right++)
//        {
//            sum += nums[right];//进窗口;
//            while (sum >= target)//判断;
//            {
//                ret = min(ret, right - left + 1);//更新结果;
//                sum -= nums[left++];//出窗口;
//            }
//        }
//        return ret == INT_MAX ? 0 : ret;
//    }
//};

//2.⽆重复字符的最⻓⼦串
//暴力解法；
//    int lengthOfLongestSubstring(string s)
//    {
//        int size = s.size();
//        int ret = 0;
//        string str;
//        for (int left = 0, right = 0; right < size; right++)
//        {
//            if (str.find(s[right])> 5000)
//            {
//                str += s[right];
//                ret = max(ret, right - left + 1);
//            }
//            else
//            {
//                left++;
//                right = left-1;
//                str = "";
//            }
//        }
//        return ret;
//    }
//// 滑动窗口;
//    class Solution {
//    public:
//        int lengthOfLongestSubstring(string s)
//        {
//            int ret = 0;
//            int hash[128] = { 0 };
//            int left = 0, right = 0;
//            int len = s.size();
//            while (right < len)
//            {
//                // 进窗口;
//                hash[s[right]]++;
//                while (hash[s[right]] > 1) //判断;
//                {
//                    hash[s[left]]--;
//                    left++;
//                }
//                ret = max(ret, right - left + 1);
//                right++;
//            }
//            return ret;
//        }
//    };


/// ////////////////3.1004.最⼤连续1的个数
//class Solution {
//public:
//    int longestOnes(vector<int>& nums, int k)
//    {
//        int left = 0, right = 0;
//        int ret = 0, size = nums.size();
//        int hash[2] = { 0 };
//        while (right < size)
//        {
//            //进窗口;
//            hash[nums[right]]++;
//            while (hash[0] > k) //判断;
//            {
//                //出窗口;
//                hash[nums[left]]--;
//                left++;
//            }
//            ret = max(ret, right - left + 1); //更新结果;
//            right++;
//        }
//        return ret;
//    }
//};

///////////////////////4.将x减到0的最⼩操作数

//好多坑;
//class Solution {
//public:
//    int minOperations(vector<int>& nums, int x)
//    {
//        int sum = 0, size = nums.size();
//        int ret = -1, left = 0, right = 0;
//        for (auto e : nums) sum += e;
//        int target = sum - x;
//        if (target < 0) return -1;
//        int add = 0;
//        while (right < size)
//        {
//            //进窗口;
//            add += nums[right];
//            while (add > target) //判断;
//            {
//                //出窗口;
//                add -= nums[left];
//                left++;
//            }
//            if (target == add) //更新结果;
//                ret = max(ret, right - left + 1);
//            right++;
//        }
//        if (ret == -1)
//            return -1;
//        return size - ret;
//    }
//};

////////////////////////5.⽔果成篮
// 
// 
// 法一：数组模拟哈希表：
//class Solution {
//public:
//    int totalFruit(vector<int>& fruits)
//    {
//        int hash[100001] = { 0 };
//        int left = 0, right = 0, kind = 0, ret = 1, size = fruits.size();
//        while (right < fruits.size())
//        {
//            //进窗口;
//            hash[fruits[right]]++;
//            if (hash[fruits[right]] == 1) kind++; //更新水果种类;
//            while (kind > 2)
//            {
//                //出窗口;
//                hash[fruits[left]]--;
//                if (hash[fruits[left]] == 0) kind--;
//                left++;
//            }
//            ret = max(ret, right - left + 1);
//            right++;
//        }
//        return ret;
//    }
//};


///  法二：使用哈希表：
//class Solution {
//public:
//    int totalFruit(vector<int>& fruits)
//    {
//        unordered_map<int, int> hash;
//        int left = 0, right = 0;
//        int ret = 1;
//        while (right < fruits.size())
//        {
//            //进窗口;
//            hash[fruits[right]]++;
//            while (hash.size() > 2)
//            {
//                //出窗口：
//                hash[fruits[left]]--;
//                if (hash[fruits[left]] == 0) hash.erase(fruits[left]);
//                left++;
//            }
//            //更新结果：
//            ret = max(ret, right - left + 1);
//            right++;
//        }
//        return ret;
//    }
//};


/////////////6.找到字符串中所有字⺟异位词
//class Solution {
//public:
//    vector<int> findAnagrams(string s, string p)
//    {
//        int hash1[26] = { 0 }; //记录p中字符
//        for (auto e : p) hash1[e - 'a']++;
//        int hash2[26] = { 0 }; //记录s中字符
//        vector<int> ret;
//        int size = p.size();
//        for (int left = 0, right = 0, count = 0; right < s.size(); right++)
//        {
//            //进窗口;
//            char in = s[right];
//            ++hash2[in - 'a'];
//            if (hash2[in - 'a'] <= hash1[in - 'a']) count++;
//            //出窗口;
//            if (right - left + 1 > size)
//            {
//                char out = s[left];
//                if (hash2[out - 'a'] <= hash1[out - 'a']) count--;
//                --hash2[out - 'a'];
//                left++;
//            }
//            if (count == size)
//                ret.push_back(left);
//        }
//        return ret;
//    }
//};

//vector<int> findAnagrams(string s, string p)
//{
//    int hash1[26] = { 0 }; //统计p中字符
//    for (auto e : p)  hash1[e - 'a']++;
//    int hash2[26] = { 0 }; //滑动窗口字符;
//    vector<int> ret;
//    int size = p.size();
//    for (int left = 0, right = 0, count = 0; right < s.size(); right++)
//    {
//        //进窗口;
//        ++hash2[s[right] - 'a'];
//        if (hash2[s[right] - 'a'] <= hash1[s[right] - 'a']) count++; //统计滑动窗口中有效字符的数量：
//        //判断;
//        if (right - left + 1 > size)
//        {
//            //出窗口;
//            if (hash2[s[left] - 'a'] <= hash1[s[left] - 'a']) count--;
//            --hash2[s[left] - 'a'];
//            left++;
//        }
//        if (count == size)
//            ret.push_back(left);
//
//    }
//    return ret;
//}






//-----------------------------------------------------------------------------------------------------


//////定长;

/////////1456. 定长子串中元音的最大数目


    bool isyuan(char ch)
    {
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
    }
    int maxvowels(string s, int k)
    {
        int ret = 0, tmp = 0;
        for (int i = 0; i < k; i++)
       {
            tmp += isyuan(s[i]);
        }
       ret = max(ret, tmp);
        for (int i = k; i < s.size(); i++)
        {
            tmp -= isyuan(s[i - k]);
            tmp += isyuan(s[i]);
            ret = max(ret, tmp);
        }
        return ret;
    }



////////643. 子数组最大平均数 I
    double findMaxAverage(vector<int>& nums, int k)
    {
        double sum = 0.0;
        double ret = -INT_MIN;
        for (int left = 0, right = 0; right < nums.size(); right++)
        {
            //进窗口;
            sum += nums[right];
            if (right < k - 1) continue;
            ret = max(ret, sum);
            //出窗口;
            sum -= nums[left++];
        }
        ret = ret / k;
        return ret;
    }



////////////1343. 大小为 K 且平均值大于等于阈值的子数组数目
class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold)
    {
        int ret = 0;
        double sum = 0;
        for (int left = 0, right = 0; right < arr.size(); right++)
        {
            //进窗口
            sum += arr[right];
            if (right < k - 1) continue;
            if ((sum / k) >= threshold) ret++;
            //出窗口;
            sum -= arr[left++];
        }
        return ret;
    }
};



vector<int> getAverages(vector<int>& nums, int k)
{
    vector<int> ret;
    int sum = 0;
    for (int left = 0, right = 0; right < nums.size(); right++)
    {
        //进窗口;
        sum += nums[right];
        if (right < k)
        {
            ret.push_back(-1);
        }
        if (right - left > 2 * k) sum -= nums[left++];
        if (right - left == 2 * k) ret.push_back(sum / (2 * k + 1));
    }
    return ret;
}

int minimumRecolors(string blocks, int k)
{
    int ret = INT_MAX, tmp = 0;
    for (int left = 0, right = 0; right < blocks.size(); right++)
    {
        //进窗口;
        if (blocks[right] == 'W') tmp++;
        //出窗口;
        if (right - left + 1 > k)
        {
            if (blocks[left++] == 'W') tmp--;
        }
        //更新结果
        if (right - left + 1 == k)
        {
            ret = min(ret, tmp);
        }
    }
    return ret;
}

///////1052. 爱生气的书店老板
int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes)
{
    int size = customers.size();
    int sum = 0;
    for (int i = 0; i < size; i++)
    {
        if (grumpy[i] == 0) sum += customers[i]; //计算初始状态的顾客数；
    }
    int ret = 0;
    for (int left = 0, right = 0; right < size; right++)
    {
        //进窗口;
        if (grumpy[right] == 1) sum += customers[right];
        //判断+出窗口;
        if (right - left + 1 > minutes)
        {
            if (grumpy[left]) sum -= customers[left];
            left++;
        }
        //更新结果;
        ret = max(ret, sum);
    }
    return ret;
}


//2841. 几乎唯一子数组的最大和
//用unordered_map解决;
long long maxSum(vector<int>& nums, int m, int k)
{
    int diff = 0;
    long long ret = 0, sum = 0;
    unordered_map<int, int> hash;
    for (int left = 0, right = 0; right < nums.size(); right++)
    {
        //进窗口：
        hash[nums[right]]++;
        sum += nums[right];
        if (hash[nums[right]] == 1) diff++;
        if (right - left + 1 > k)
        {
            //出窗口：
            hash[nums[left]]--;
            if (!hash[nums[left]]) diff--;
            sum -= nums[left++];
        }
        //更新结果：
        if (diff >= m) ret = max(ret, sum);
    }
    return ret;
}


vector<int> findAnagrams(string s, string p)
{
    int hash1[26] = { 0 };//统计p
    for (auto e : p) hash1[e - 'a']++;
    int hash2[26] = { 0 }; //统计s；
    int count = 0;
    vector<int> ret;
    for (int left = 0, right = 0; right < s.size(); right++)
    {
        //进窗口：
        ++hash2[s[right] - 'a'];
        if (hash2[s[right] - 'a'] <= hash1[s[right] - 'a']) count++;
        //判断+出窗口：
        if (right - left + 1 > p.size())
        {
            //出窗口：
            if (hash2[s[left] - 'a'] <= hash1[s[left] - 'a']) count--;
            left++;
        }
        //更新结果;
        if (count == p.size()) ret.push_back(left);
    }
    return ret;
}





/////////////////不定长;

//3090. 每个字符最多出现两次的最长子字符串
int maximumLengthSubstring(string s)
{
    unordered_map<int, int> hash;
    int ret = 0, count = 0;
    for (int left = 0, right = 0; right < s.size(); right++)
    {
        //进窗口：
        hash[s[right]]++;
        while (hash[s[right]] > 2)
        {
            //出窗口;
            hash[s[left]]--;
            left++;
        }
        //更新结果：
        ret = max(ret, right - left + 1);
    }
    return ret;
}


///////1658. 将 x 减到 0 的最小操作数
int minOperations(vector<int>& nums, int x)
{
    int ret = INT_MIN;
    long long sum = 0;
    for (auto e : nums) sum += e;
    if (sum - x < 0) return -1;
    long long tmp = 0;//记录窗口中数据的和;
    for (int left = 0, right = 0; right < nums.size(); right++)
    {
        //进窗口；
        tmp += nums[right];
        while (tmp > sum - x)
        {
            //出窗口;
            tmp -= nums[left];
            left++;
        }
        //更新结果;
        if (tmp == sum - x) ret = max(ret, right - left + 1);
    }
    return ret == INT_MIN ? -1 : nums.size() - ret;
}


/////1658. 将 x 减到 0 的最小操作数
int maximumUniqueSubarray(vector<int>& nums)
{
    map<int, int> hash;
    int ret = 0, tmp = 0;
    for (int left = 0, right = 0; right < nums.size(); right++)
    {
        //进窗口;
        hash[nums[right]]++;
        tmp += nums[right];
        //出窗口：
        while (hash[nums[right]] > 1)
        {
            tmp -= nums[left];
            hash[nums[left]]--;
            left++;
        }
        ret = max(ret, tmp);
    }
    return ret;
}

/////2958. 最多 K 个重复元素的最长子数组
int maxSubarrayLength(vector<int>& nums, int k)
{
    int ret = 0;
    map<int, int>hash;
    for (int left = 0, right = 0; right < nums.size(); right++)
    {
        //进窗口：
        hash[nums[right]]++;
        while (hash[nums[right]] > k)
        {
            //出窗口;
            hash[nums[left]]--;
            left++;
        }
        //更新结果：
        ret = max(ret, right - left + 1);
    }
    return ret;
}

//2779. 数组的最大美丽值△△
int maximumBeauty(vector<int>& nums, int k)
{
    sort(nums.begin(), nums.end());
    int ret = 0;
    for (int left = 0, right = 0; right < nums.size(); right++)
    {
        while (nums[right] - nums[left] > 2 * k)
        {
            left++;
        }
        ret = max(ret, right - left + 1);
    }
    return ret;
}



//1838. 最高频元素的频数 △△
int maxFrequency(vector<int>& nums, int k)
{
    sort(nums.begin(), nums.end());
    long long sum = 0; long long _max = 0;
    int ret = 0;
    for (int left = 0, right = 0; right < nums.size(); right++)
    {
        sum += nums[right];
        _max = (long long)nums[right] * (right - left + 1);
        while (_max - sum > k)
        {
            sum -= nums[left];
            left++;
            _max -= nums[right];
        }
        ret = max(ret, right - left + 1);
    }
    return ret;
}
int main()
{  
    string s{ "cbaebabacd " };
    string p{ "abc" };
    findAnagrams(s, p);
    return 0;
}